home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus Leser 19 / Amiga Plus Leser CD 19.iso / Tools / MorphOS / cvs-1.11.2 / source / amiga / ssh / rsa.c < prev    next >
Encoding:
C/C++ Source or Header  |  2002-11-18  |  9.1 KB  |  481 lines
  1. /*
  2.  * RSA implementation just sufficient for ssh client-side
  3.  * initialisation step
  4.  *
  5.  * Rewritten for more speed by Joris van Rantwijk, Jun 1999.
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11.  
  12. #include "ssh.h"
  13. #include "rsa.h"
  14.  
  15. typedef unsigned short *Bignum;
  16.  
  17. #if defined TESTMODE || defined RSADEBUG
  18. #ifndef DLVL
  19. #define DLVL 10000
  20. #endif
  21. #define debug(x) bndebug(#x,x)
  22. static int level = 0;
  23. static void 
  24. bndebug (char *name, Bignum b)
  25. {
  26.   int i;
  27.   int w = 50 - level - strlen (name) - 5 * b[0];
  28.   if (level >= DLVL)
  29.     return;
  30.   if (w < 0)
  31.     w = 0;
  32.   printf ("%*s%s%*s", level, "", name, w, "");
  33.   for (i = b[0]; i > 0; i--)
  34.     printf (" %04x", b[i]);
  35.   printf ("\n");
  36. }
  37. #define dmsg(x) do {if(level<DLVL){printf("%*s",level,"");printf x;}} while(0)
  38. #define enter(x) do { dmsg(x); level += 4; } while(0)
  39. #define leave(x) do { level -= 4; dmsg(x); } while(0)
  40. #else
  41. #define debug(x)
  42. #define dmsg(x)
  43. #define enter(x)
  44. #define leave(x)
  45. #endif
  46.  
  47. static Bignum 
  48. newbn (int length)
  49. {
  50.   Bignum b = malloc ((length + 1) * sizeof (unsigned short));
  51.   if (!b)
  52.     abort ();                   /* FIXME */
  53.   b[0] = length;
  54.   return b;
  55. }
  56.  
  57. static void 
  58. freebn (Bignum b)
  59. {
  60.   free (b);
  61. }
  62.  
  63. /*
  64.  * Compute c = a * b.
  65.  * Input is in the first len words of a and b.
  66.  * Result is returned in the first 2*len words of c.
  67.  */
  68. static void 
  69. bigmul (unsigned short *a, unsigned short *b, unsigned short *c, int len)
  70. {
  71.   int i, j;
  72.   unsigned long ai, t;
  73.  
  74.   for (j = len - 1; j >= 0; j--)
  75.     c[j + len] = 0;
  76.  
  77.   for (i = len - 1; i >= 0; i--)
  78.   {
  79.     ai = a[i];
  80.     t = 0;
  81.     for (j = len - 1; j >= 0; j--)
  82.     {
  83.       t += ai * (unsigned long) b[j];
  84.       t += (unsigned long) c[i + j + 1];
  85.       c[i + j + 1] = (unsigned short) t;
  86.       t = t >> 16;
  87.     }
  88.     c[i] = (unsigned short) t;
  89.   }
  90. }
  91.  
  92. /*
  93.  * Compute a = a % m.
  94.  * Input in first 2*len words of a and first len words of m.
  95.  * Output in first 2*len words of a (of which first len words will be zero).
  96.  * The MSW of m MUST have its high bit set.
  97.  */
  98. static void 
  99. bigmod (unsigned short *a, unsigned short *m, int len)
  100. {
  101.   unsigned short m0, m1;
  102.   unsigned int h;
  103.   int i, k;
  104.  
  105.   /* Special case for len == 1 */
  106.   if (len == 1)
  107.   {
  108.     a[1] = (((long) a[0] << 16) + a[1]) % m[0];
  109.     a[0] = 0;
  110.     return;
  111.   }
  112.  
  113.   m0 = m[0];
  114.   m1 = m[1];
  115.  
  116.   for (i = 0; i <= len; i++)
  117.   {
  118.     unsigned long t;
  119.     unsigned int q, r, c;
  120.  
  121.     if (i == 0)
  122.     {
  123.       h = 0;
  124.     }
  125.     else
  126.     {
  127.       h = a[i - 1];
  128.       a[i - 1] = 0;
  129.     }
  130.  
  131.     /* Find q = h:a[i] / m0 */
  132.     t = ((unsigned long) h << 16) + a[i];
  133.     q = t / m0;
  134.     r = t % m0;
  135.  
  136.     /* Refine our estimate of q by looking at
  137.        h:a[i]:a[i+1] / m0:m1 */
  138.     t = (long) m1 *(long) q;
  139.     if (t > ((unsigned long) r << 16) + a[i + 1])
  140.     {
  141.       q--;
  142.       t -= m1;
  143.       r = (r + m0) & 0xffff;    /* overflow? */
  144.       if (r >= (unsigned long) m0 &&
  145.           t > ((unsigned long) r << 16) + a[i + 1])
  146.         q--;
  147.     }
  148.  
  149.     /* Substract q * m from a[i...] */
  150.     c = 0;
  151.     for (k = len - 1; k >= 0; k--)
  152.     {
  153.       t = (long) q *(long) m[k];
  154.       t += c;
  155.       c = t >> 16;
  156.       if ((unsigned short) t > a[i + k])
  157.         c++;
  158.       a[i + k] -= (unsigned short) t;
  159.     }
  160.  
  161.     /* Add back m in case of borrow */
  162.     if (c != h)
  163.     {
  164.       t = 0;
  165.       for (k = len - 1; k >= 0; k--)
  166.       {
  167.         t += m[k];
  168.         t += a[i + k];
  169.         a[i + k] = (unsigned short) t;
  170.         t = t >> 16;
  171.       }
  172.     }
  173.   }
  174. }
  175.  
  176. /*
  177.  * Compute (base ^ exp) % mod.
  178.  * The base MUST be smaller than the modulus.
  179.  * The most significant word of mod MUST be non-zero.
  180.  * We assume that the result array is the same size as the mod array.
  181.  */
  182. static void 
  183. modpow (Bignum base, Bignum exp, Bignum mod, Bignum result)
  184. {
  185.   unsigned short *a, *b, *n, *m;
  186.   int mshift;
  187.   int mlen, i, j;
  188.  
  189.   /* Allocate m of size mlen, copy mod to m */
  190.   /* We use big endian internally */
  191.   mlen = mod[0];
  192.   m = malloc (mlen * sizeof (unsigned short));
  193.   for (j = 0; j < mlen; j++)
  194.     m[j] = mod[mod[0] - j];
  195.  
  196.   /* Shift m left to make msb bit set */
  197.   for (mshift = 0; mshift < 15; mshift++)
  198.     if ((m[0] << mshift) & 0x8000)
  199.       break;
  200.   if (mshift)
  201.   {
  202.     for (i = 0; i < mlen - 1; i++)
  203.       m[i] = (m[i] << mshift) | (m[i + 1] >> (16 - mshift));
  204.     m[mlen - 1] = m[mlen - 1] << mshift;
  205.   }
  206.  
  207.   /* Allocate n of size mlen, copy base to n */
  208.   n = malloc (mlen * sizeof (unsigned short));
  209.   i = mlen - base[0];
  210.   for (j = 0; j < i; j++)
  211.     n[j] = 0;
  212.   for (j = 0; j < base[0]; j++)
  213.     n[i + j] = base[base[0] - j];
  214.  
  215.   /* Allocate a and b of size 2*mlen. Set a = 1 */
  216.   a = malloc (2 * mlen * sizeof (unsigned short));
  217.   b = malloc (2 * mlen * sizeof (unsigned short));
  218.   for (i = 0; i < 2 * mlen; i++)
  219.     a[i] = 0;
  220.   a[2 * mlen - 1] = 1;
  221.  
  222.   /* Skip leading zero bits of exp. */
  223.   i = 0;
  224.   j = 15;
  225.   while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0)
  226.   {
  227.     j--;
  228.     if (j < 0)
  229.     {
  230.       i++;
  231.       j = 15;
  232.     }
  233.   }
  234.  
  235.   /* Main computation */
  236.   while (i < exp[0])
  237.   {
  238.     while (j >= 0)
  239.     {
  240.       bigmul (a + mlen, a + mlen, b, mlen);
  241.       bigmod (b, m, mlen);
  242.       if ((exp[exp[0] - i] & (1 << j)) != 0)
  243.       {
  244.         bigmul (b + mlen, n, a, mlen);
  245.         bigmod (a, m, mlen);
  246.       }
  247.       else
  248.       {
  249.         unsigned short *t;
  250.         t = a;
  251.         a = b;
  252.         b = t;
  253.       }
  254.       j--;
  255.     }
  256.     i++;
  257.     j = 15;
  258.   }
  259.  
  260.   /* Fixup result in case the modulus was shifted */
  261.   if (mshift)
  262.   {
  263.     for (i = mlen - 1; i < 2 * mlen - 1; i++)
  264.       a[i] = (a[i] << mshift) | (a[i + 1] >> (16 - mshift));
  265.     a[2 * mlen - 1] = a[2 * mlen - 1] << mshift;
  266.     bigmod (a, m, mlen);
  267.     for (i = 2 * mlen - 1; i >= mlen; i--)
  268.       a[i] = (a[i] >> mshift) | (a[i - 1] << (16 - mshift));
  269.   }
  270.  
  271.   /* Copy result to buffer */
  272.   for (i = 0; i < mlen; i++)
  273.     result[result[0] - i] = a[i + mlen];
  274.  
  275.   /* Free temporary arrays */
  276.   for (i = 0; i < 2 * mlen; i++)
  277.     a[i] = 0;
  278.   free (a);
  279.   for (i = 0; i < 2 * mlen; i++)
  280.     b[i] = 0;
  281.   free (b);
  282.   for (i = 0; i < mlen; i++)
  283.     m[i] = 0;
  284.   free (m);
  285.   for (i = 0; i < mlen; i++)
  286.     n[i] = 0;
  287.   free (n);
  288. }
  289.  
  290. int 
  291. makekey (unsigned char *data, R_RSAKey * result, unsigned char **keystr)
  292. {
  293.   unsigned char *p = data;
  294.   Bignum bn[2];
  295.   int i, j;
  296.   int w, b;
  297.  
  298.   result->bits = 0;
  299.   for (i = 0; i < 4; i++)
  300.     result->bits = (result->bits << 8) + *p++;
  301.  
  302.   for (j = 0; j < 2; j++)
  303.   {
  304.  
  305.     w = 0;
  306.     for (i = 0; i < 2; i++)
  307.       w = (w << 8) + *p++;
  308.  
  309.     result->bytes = b = (w + 7) / 8;  /* bits -> bytes */
  310.     w = (w + 15) / 16;          /* bits -> words */
  311.  
  312.     bn[j] = newbn (w);
  313.  
  314.     if (keystr)
  315.       *keystr = p;              /* point at key string, second time */
  316.  
  317.     for (i = 1; i <= w; i++)
  318.       bn[j][i] = 0;
  319.     for (i = b; i--;)
  320.     {
  321.       unsigned char byte = *p++;
  322.       if (i & 1)
  323.         bn[j][1 + i / 2] |= byte << 8;
  324.       else
  325.         bn[j][1 + i / 2] |= byte;
  326.     }
  327.  
  328.     debug (bn[j]);
  329.  
  330.   }
  331.  
  332.   result->exponent = bn[0];
  333.   result->modulus = bn[1];
  334.  
  335.   return p - data;
  336. }
  337.  
  338. void 
  339. rsaencrypt (unsigned char *data, int length, R_RSAKey * key)
  340. {
  341.   Bignum b1, b2;
  342.   int w, i;
  343.   unsigned char *p;
  344.  
  345.   debug (key->exponent);
  346.  
  347.   memmove (data + key->bytes - length, data, length);
  348.   data[0] = 0;
  349.   data[1] = 2;
  350.  
  351.   for (i = 2; i < key->bytes - length - 1; i++)
  352.   {
  353.     do
  354.     {
  355.       data[i] = rand () % 256;
  356.     }
  357.     while (data[i] == 0);
  358.   }
  359.   data[key->bytes - length - 1] = 0;
  360.  
  361.   w = (key->bytes + 1) / 2;
  362.  
  363.   b1 = newbn (w);
  364.   b2 = newbn (w);
  365.  
  366.   p = data;
  367.   for (i = 1; i <= w; i++)
  368.     b1[i] = 0;
  369.   for (i = key->bytes; i--;)
  370.   {
  371.     unsigned char byte = *p++;
  372.     if (i & 1)
  373.       b1[1 + i / 2] |= byte << 8;
  374.     else
  375.       b1[1 + i / 2] |= byte;
  376.   }
  377.  
  378.   debug (b1);
  379.  
  380.   modpow (b1, key->exponent, key->modulus, b2);
  381.  
  382.   debug (b2);
  383.  
  384.   p = data;
  385.   for (i = key->bytes; i--;)
  386.   {
  387.     unsigned char b;
  388.     if (i & 1)
  389.       b = b2[1 + i / 2] >> 8;
  390.     else
  391.       b = b2[1 + i / 2] & 0xFF;
  392.     *p++ = b;
  393.   }
  394.  
  395.   freebn (b1);
  396.   freebn (b2);
  397. }
  398.  
  399. static int 
  400. rsastr_len (R_RSAKey * key)
  401. {
  402.   Bignum md, ex;
  403.  
  404.   md = key->modulus;
  405.   ex = key->exponent;
  406.   return 4 * (ex[0] + md[0]) + 10;
  407. }
  408.  
  409. static void 
  410. rsastr_fmt (char *str, R_RSAKey * key)
  411. {
  412.   Bignum md, ex;
  413.   int len = 0, i;
  414.  
  415.   md = key->modulus;
  416.   ex = key->exponent;
  417.  
  418.   for (i = 1; i <= ex[0]; i++)
  419.   {
  420.     sprintf (str + len, "%04x", ex[i]);
  421.     len += strlen (str + len);
  422.   }
  423.   str[len++] = '/';
  424.   for (i = 1; i <= md[0]; i++)
  425.   {
  426.     sprintf (str + len, "%04x", md[i]);
  427.     len += strlen (str + len);
  428.   }
  429.   str[len] = '\0';
  430. }
  431.  
  432. #ifdef TESTMODE
  433.  
  434. #ifndef NODDY
  435. #define p1 10007
  436. #define p2 10069
  437. #define p3 10177
  438. #else
  439. #define p1 3
  440. #define p2 7
  441. #define p3 13
  442. #endif
  443.  
  444. unsigned short P1[2] = {1, p1};
  445. unsigned short P2[2] = {1, p2};
  446. unsigned short P3[2] = {1, p3};
  447. unsigned short bigmod[5] = {4, 0, 0, 0, 32768U};
  448. unsigned short mod[5] = {4, 0, 0, 0, 0};
  449. unsigned short a[5] = {4, 0, 0, 0, 0};
  450. unsigned short b[5] = {4, 0, 0, 0, 0};
  451. unsigned short c[5] = {4, 0, 0, 0, 0};
  452. unsigned short One[2] = {1, 1};
  453. unsigned short Two[2] = {1, 2};
  454.  
  455. int 
  456. main (void)
  457. {
  458.   modmult (P1, P2, bigmod, a);
  459.   debug (a);
  460.   modmult (a, P3, bigmod, mod);
  461.   debug (mod);
  462.  
  463.   sub (P1, One, a);
  464.   debug (a);
  465.   sub (P2, One, b);
  466.   debug (b);
  467.   modmult (a, b, bigmod, c);
  468.   debug (c);
  469.   sub (P3, One, a);
  470.   debug (a);
  471.   modmult (a, c, bigmod, b);
  472.   debug (b);
  473.  
  474.   modpow (Two, b, mod, a);
  475.   debug (a);
  476.  
  477.   return 0;
  478. }
  479.  
  480. #endif
  481.